// 根据一棵树的中序遍历与后序遍历构造二叉树。

// 注意:
// 你可以假设树中没有重复的元素。

// 例如，给出

// 中序遍历 inorder = [9,3,15,20,7]
// 后序遍历 postorder = [9,15,7,20,3]
// 返回如下的二叉树：

//     3
//    / \
//   9  20
//     /  \
//    15   7


/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */


// ===================利用postorder的每一个元素都是对应递归子树的根节点==============
var buildTree = function (inorder, postorder) {
  // 倒着扫描
  let cursor = postorder.length - 1;
  let build = (inorder) => {
    if (inorder.length !== 0) {
      let
        rootVal = postorder[cursor],
        rootIndex = inorder.indexOf(rootVal),
        root = new TreeNode(rootVal);
      cursor--;
      if (rootIndex === 0) {
        root.right = build(inorder.slice(rootIndex + 1));
        root.left = null;
      }
      else if (rootIndex === inorder.length - 1) {
        root.right = null;
        root.left = build(inorder.slice(0, rootIndex));
      }
      else {
        // 注意要先生成右子树，再生成左子树，才能保证cursor的顺序扫描
        root.right = build(inorder.slice(rootIndex + 1));
        root.left = build(inorder.slice(0, rootIndex));
      }
      return root;
    }
    return null;
  }
  return build(inorder)
};



// ============================传统方法：处理下标===============================
var buildTree = function (inorder, postorder) {
  let build = (inorder, in_start, in_end, postorder, post_start, post_end) => {
    if (post_start > post_end) return null;
    let
      // 从后开始处理
      rootVal = postorder[post_end],
      rootIndex = inorder.indexOf(rootVal),
      root = new TreeNode(rootVal),
      rightSize = in_end - rootIndex;
    root.right = build(inorder, rootIndex + 1, in_end, postorder, post_end - rightSize, post_end - 1);
    root.left = build(inorder, in_start, rootIndex - 1, postorder, post_start, post_end - rightSize - 1);
    return root;
  };
  return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
};